package d2;
import java.util.*;

public class Day10 {


    public static void main(String[] args) {
        int[][] ret = {{0,0,0},{0,1,0},{1,1,1}};
        updateMatrix(ret);
    }
    //01矩阵
    public static int[][] updateMatrix(int[][] mat) {
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        int m=mat.length,n=mat[0].length;
        int[][] dist = new int[m][n];
        Queue<int[]> q = new LinkedList<>();
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(mat[i][j]==0) {
                    dist[i][j]=0;
                    q.add(new int[]{i,j});
                }else dist[i][j]=-1;
        while(!q.isEmpty()) {
            int[] t = q.poll();
            int a=t[0],b=t[1];
            for(int i=0;i<4;i++) {
                int x=a+dx[i],y=b+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n && dist[x][y]==-1) {
                    dist[x][y]=dist[a][b]+1;
                    q.add(new int[]{x,y});
                }
            }
        }
        return dist;
    }

    public static void main3(String[] args) {
        String s = "bbab";
        checkPartitioning(s);
    }
    //分割回文串Ⅵ
    public static boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        char[] arr = s.toCharArray();
        for(int i=n-1;i>=0;i--) {
            for(int j=i;j<n;j++) {
                if(arr[i]==arr[j]) {
                    if(i==j) dp[i][j]=true;
                    else if(i+1==j) dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                }
            }
        }
        for(int x=1;x<n-1;x++) {
            for(int y=x+1;y<n;y++) {
                if(dp[0][x-1] && dp[x][y-1] && dp[y][n-1]) return true;
            }
        }
        return false;
    }
    public static void main1(String[] args) {
//        List<List<Integer>> forest = new ArrayList<>();
//        forest.get(0).size();
//        forest.get(0).get(1);
//        int ma = Integer.MAX_VALUE;
        List<Integer> list=new ArrayList<>();
        list.add(10);
        list.add(9);
        list.add(18);
        Collections.sort(list);
        for(int x:list) {
            System.out.println(x);
        }
    }

    public static void main2(String[] args) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> ret = new ArrayList<>();
        ret.add(1);
        ret.add(2);
        ret.add(3);
        list.add(ret);
        List<Integer> ret1 = new ArrayList<>();
        ret1.add(0);
        ret1.add(0);
        ret1.add(0);
        list.add(ret1);
        List<Integer> ret2 = new ArrayList<>();
        ret2.add(7);
        ret2.add(6);
        ret2.add(5);
        list.add(ret2);
        //int num = cutOffTree(list);
    }

    //为高尔夫比赛砍树
    int m,n;
    public int cutOffTree(List<List<Integer>> f) {
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        m = f.size();n = f.get(0).size();
        //1.获取每一棵树的下标
        List<int[]> list = new ArrayList<>();//存取待砍树的下标
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(f.get(i).get(j)>1)
                    list.add(new int[]{i,j});
        //2.按照下标对应的值进行排序
        Collections.sort(list,(a,b)->{
            return f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]);
        });
        //3.开始砍树
        int sx=0,sy=0;//开始的位置
        int ret = 0;
        for(int[] t : list) {
            int ex=t[0],ey=t[1];
            //寻找从起点到终点的最短路径
            int step = bfs(f,sx,sy,ex,ey);
            if(step==-1) return -1;
            ret += step;
            //更新起始位置
            sx=ex;
            sy=ey;
        }
        return ret;
    }
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,-1,1};
    public int bfs(List<List<Integer>> f,int sx,int sy,int ex,int ey) {
        if(sx==ex && sy==ey) return 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sx,sy});
        int step=0;
        boolean[][] vis = new boolean[m][n];
        while(!q.isEmpty()) {
            int sz = q.size();
            step++;
            while(sz-- != 0) {
                int[] t = q.poll();
                int a = t[0],b = t[1];
                for(int k=0;k<4;k++) {
                    int x=a+dx[k],y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n && f.get(x).get(y)>0 &&!vis[x][y]) {
                        if(x==ex && y==ey) return step;
                        q.add(new int[]{x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;
    }
}
